1. Field of Invention
The present invention relates to a method for video compression, and more particularly, to a method for motion search between video frames with multiple blocks.
2. Description of the Related Art
In recent years, the popularity in network and the progress in the multimedia transmission technique make the exchange of video data indispensable in our daily life. To use the limited transmission bandwidth effectively for transmitting video data with the most contents and the best quality, it is necessary to adopt the most advanced method for compressing video and data. Among the currently available image compression technologies, the standard H.264 is the most advanced one, which was established by the incorporation of the Video Coding Experts Group Alliance (VCEG-Alliance) of International Telecommunication Union (ITU) and the Moving Picture Experts Group Alliance (MPEG-Alliance) of International Electrotechnical Commission (IEC) affiliated by International Organization for Standardization (ISO).
The major objective of H.264 is to effectively advance the compression rate of video data for a better effect of video data transmission on a network. In comparison with the previous standard H.263 plus or the MPEG-4, H.264 saves a compression rate with approximate 50%, and has a higher quality. Although H.264 has a higher compression rate and better compression quality, it still requires a huge computation due to multiple configurations of blocks and multiple referencing the standard supports. Wherein, the computation of motion estimation takes over 80% of the entire computation, therefore, a good motion estimation algorithm is essential to decrease the computation thereof.
Among the methods for searching the best motion vector, full search (FS) is one of them that searches all the points within a search range. Through the FS, a block with the least error is obtained, but the complexity of the FS is also rised correspondingly. To overcome the disadvantage, a lot of algorithms were provided, for example, diamond search (DS), diamond search (DS), and so on.
FIG. 1 is a diagram showing a search pattern with hexagon-based search (HEXBS) algorithm, wherein a center point 100, two search points 110 and 120 having a distance of 2 from the center point 100 and located at the upper side and the lower side of the center point 100, respectively, and four search points 130, 140, 150 and 160 having a distance of √{square root over (5)} from the center point 100 and located at the upper-left side, the lower-left side, the upper-right side and the lower-right side of the center point 100, respectively, are included. The algorithm computes the image error values of the blocks belong to the seven search points respectively, so as to find out the least-error block with the least error value. Then, the search point corresponding to the least-error block is taken as a new center point for restarting a new search until the center-point block becomes the least-error block. Although the above-described HEXBS algorithm has search points less than the FS, it is still not sufficient to catch the increasing speed of the resolution and the capacity of current video files. Therefore, how to effectively advance the speed of motion estimation searching between video frames has become one of the significant projects desired to be solved in video compression technique today.